package com.tree;

/**
 * 第一次优化:
 * 通过基本的代码实现,可以知道,在进行合并操作时是十分复杂的,
 * 在每次合并时都既要遍历一遍数组,还要逐一判断,并且对部分数据赋值.
 * <p>
 * 进行改进:
 * 数组中保存的内容不再是自己的组别,而是随机的一个与自己连接的元素的下标,
 * 这次改进后的数组更像是一颗从孩子节点指向父节点的数
 */
public class UnionFindImpl_2 implements IUnionFind {
    int[] unionArr; //使用数组下标表示元素,数组值表示与自己连接的一个元素的下标
    int count;  //表示元素个数

    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot != qRoot) {
            //只需要让 p 与 q 的父节点中的一个指向另一个即可(unionArr[pRoot] = qRoot)
            //这样,p 与 q 就有相同的父节点,表示他们两个连接在一起
            unionArr[pRoot] = qRoot;
        }

    }

    @Override
    //通过不断的深入搜索自己的根节点
    public int find(int p) {
        assert (p >= 0 && p < count);
        //如果 当前的元素 = 当前元素下标 ,表示这是这个树的根节点
        while (unionArr[p] != p) {
            //从这里可以看出,每一层的 unionArr[] 都表示 内层的节点 与 外层的节点相连接
            p = unionArr[p];
        }
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        //判断 p 与 q 的父节点是否相等,就可以得到这两个节点是否已经
        return find(p) == find(q);
    }

    public UnionFindImpl_2(int count) {
        this.count = count;
        unionArr = new int[count];
        //在初始条件下,每个数据都属于不同的组别
        for (int i = 0; i < count; i++) {
            unionArr[i] = i;
        }
    }


}
